/*
 * @lc app=leetcode.cn id=121 lang=java
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
class Solution {
    public int maxProfit(int[] prices) {
        //基于动态规划的思想
        //dp[i][0]代表第i天不持有股票时最大的利润，可以有两种情况：
        //第i-1天不持有，第i天保持；第i-1天持有，第i天卖出
        //dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
        //dp[i][1]代表第i天持有股票时最大的利润，可以有两种情况：
        //第i-1天不持有（此时利润为0），第i天买入；第i-1天持有，第i天保持
        //dp[i][1]=Math.max(-prices[i],dp[i-1][1])
        //可以看出dp递推从前往后，且只依赖于前一状态，可以采用滚动数组
        int[][] dp=new int[2][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i%2][0]=Math.max(dp[(i-1)%2][0],dp[(i-1)%2][1]+prices[i]);
            dp[i%2][1]=Math.max(-prices[i],dp[(i-1)%2][1]);
        }
        return dp[(prices.length-1)%2][0];//题目说的了肯定是不持有时利润最大
    }
}
// @lc code=end

